class Node:
    def __init__(self, akey, data=None):
        self.NEXT = self
        self.PREV = self
        self._data = data
        self._key = akey

    def next(self, nextNode=-1):
        if -1 == nextNode:
            return self.NEXT
        self.NEXT = nextNode

    def prev(self, prevNode=-1):
        if -1 == prevNode:
            return self.PREV
        self.PREV = prevNode

    def data(self, mydata=None):
        if not mydata:
            return self._data
        self._data = mydata

    def key(self, akey=None):
        if not akey:
            return self._key
        self._key =  akey

class LinkedList:
    def __init__(self, Type='circular'):
        if Type == 'circular':
            self.LIST = CircularDoubleLinkedList()
        else:
            self.LIST = CircularDoubleLinkedList()
        self._traverseList = self.LIST._traverseList

    def __str__(self):
        return str(self.LIST)

    def insert(self, key, sat_data):
        self.LIST.insert(key, sat_data)

    def insertNode(self, node):
        self.LIST.insertNode(node)

    def insertAfter(self, aNode, key, sat_data):
        self.LIST.insertAfter(aNode, key, sat_data)

    def insertNodeAfter(self, aNode, node):
        self.LIST.insertNodeAfter(aNode, node)

    def search(self, key, want_data=False, want_node=False):
        return self.LIST.search(key, want_data, want_node)

    def delete(self, aNode):
        self.LIST.delete(aNode)

class CircularDoubleLinkedList:
    def __init__(self):
        self.CDLL = None            # C[ircular]D[ouble]L[inked]L[ist]
        self.SENT = Node('SENTINEL')
        self.SENT.next(self.SENT.prev())
        self.SENT.prev(self.SENT.next())

    def __str__(self):
        string = []
        searchComplete = False
        node, endkey = self.CDLL, self.CDLL.prev().key()
        while searchComplete == False:
            string.append((node.key(), node.data()))
            if node.key() == endkey:
                searchComplete = True
            node = node.next()
        return str(string)

    def insert(self, key, sat_data):
        newNode = Node(key)
        newNode.data(sat_data)
        if self.CDLL == None:
            self.CDLL = newNode
            self.CDLL.next(self.CDLL.prev())
            self.CDLL.prev(self.CDLL.next())
        else:
            newNode.prev(self.CDLL)
            newNode.next(self.CDLL.next())
            self.CDLL.next().prev(newNode)
            self.CDLL.next(newNode)

    def insertNode(self, node):
        if self.CDLL == None:
            self.CDLL = node
            self.CDLL.next(self.CDLL.prev())
            self.CDLL.prev(self.CDLL.next())
        else:
            node.prev(self.CDLL)
            node.next(self.CDLL.next())
            self.CDLL.next().prev(node)
            self.CDLL.next(node)

    def insertAfter(self, aNode, key, sat_data):
        if self.CDLL == None:
            self.insert(key, sat_data)
            return
        newNode = Node(key)
        newNode.data(sat_data)
        newNode.next(aNode.next())
        newNode.prev(aNode)
        aNode.next().prev(newNode)
        aNode.next(newNode)

    def insertNodeAfter(self, aNode, node):
        if aNode == None:
            if self.CDLL == None:
                self.insertNode(node)
                return
            aNode = self.CDLL
        node.next(aNode.next())
        node.prev(aNode)
        aNode.next().prev(node)
        aNode.next(node)

    def search(self, akey, want_data=False, want_node=False):
        searchComplete = False
        node, endkey = self.CDLL, self.CDLL.prev().key()
        while searchComplete == False:
            if node.key() == akey:
                if want_data == True and want_node == True:
                    return (node.data(), node)
                elif want_data == True:
                    return node.data()
                elif want_node == True:
                    return node
                else:
                    return True
            if node.key() == endkey:
                searchComplete = True
            node = node.next()
        return False

    def delete(self, aNode):
        aNode.prev().next(aNode.next())
        aNode.next().prev(aNode.prev())

    def _traverseList(self, aNode=None, direction=0):
        if aNode == None:
            if self.CDLL == None:
                yield None
            aNode = self.CDLL
        if direction == 0:  end = aNode.prev()
        else:               end = aNode.next()
        while True:
            yield aNode
            if aNode == end:
                break
            if direction == 0:  aNode = aNode.next()
            else:               aNode = aNode.prev()
